首页    技术博客    PHP教程    数据库技术    前端开发   HTML5    Nginx    php论坛
新用户注册 | 会员登录
加入会员，解锁专属内容
取消
热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

方阵|回路_HDU2859Phalanx(动态规划/哈希表)

作者：手机用户2502856053 | 来源：互联网 | 2024-10-09 15:39
篇首语：本文由编程笔记#小编为大家整理，主要介绍了HDU-2859Phalanx(动态规划/哈希表)相关的知识，希望对你有一定的参考价值。题目链接：点

篇首语：本文由编程笔记#小编为大家整理，主要介绍了HDU - 2859 Phalanx(动态规划/哈希表)相关的知识，希望对你有一定的参考价值。


题目链接&＃xff1a;点击查看

题目大意&＃xff1a;给定一个整数n&＃xff0c;然后给出一个n*n的方阵&＃xff0c;求方阵中最大的对称子方阵&＃xff08;对称指的是以右上角至左下角为对角线&＃xff09;

分析&＃xff1a;这个题网上有个一般做法&＃xff0c;相当于一个动态规划的小模拟&＃xff0c;时间复杂度为&＃xff0c;这里不再赘述&＃xff0c;一会直接上代码。

然后还有一个方法&＃xff0c;是那天讲题的时候&＃xff0c;鑫爷以非同常人的脑回路提出的&＃xff0c;可以先用打一个哈希表&＃xff0c;然后再遍历每一个点进行

判断&＃xff0c;如果判断相等则直接更新&＃xff0c;如果不相等则可以二分查找最长的相等子序列&＃xff0c;这样时间复杂度就下降到了logn了&＃xff0c;提交的

时候比一般方法快了十倍还多&＃xff0c;不得感叹真的tql。

直接上代码吧&＃xff1a;


一般做法&＃xff1a;

#include<iostream>
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int inf&＃61;0x3f3f3f3f;
const int N&＃61;1e3&＃43;100;
char maze[N][N];
int dp[N][N];
int main()
// freopen("input.txt","r",stdin);
int n;
while(scanf("%d",&n)!&＃61;EOF&&n)

for(int i&＃61;0;i scanf("%s",maze&＃43;i);
fill(dp[0],dp[0]&＃43;N*N,1);
int ans&＃61;1;
for(int i&＃61;1;i for(int j&＃61;0;j
int x&＃61;i;
int y&＃61;j;
while(maze[x][j]&＃61;&＃61;maze[i][y])

x--;
y&＃43;&＃43;;
if(x<0||y>&＃61;n)
break;

x&＃61;i-x;//所记录的最长相等子序列的长度
if(x>dp[i-1][j&＃43;1])

dp[i][j]&＃61;dp[i-1][j&＃43;1]&＃43;1;

else
dp[i][j]&＃61;x;
ans&＃61;max(dp[i][j],ans);

cout<











return 0;
哈希表&＃43;二分&＃xff1a;

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int inf&＃61;0x3f3f3f3f;
const int N&＃61;1e3&＃43;100;
ULL p[N],hash_1[N][N],hash_2[N][N];
char maze[N][N];
int dp[N][N];
void hash_(int n)
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;)

hash_1[i][j]&＃61;hash_1[i][j-1]*131&＃43;(maze[i][j]-&＃39;a&＃39;&＃43;1);

for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;)
for(int i&＃61;n;i>&＃61;1;i--)

hash_2[i][j]&＃61;hash_2[i&＃43;1][j]*131&＃43;(maze[i][j]-&＃39;a&＃39;&＃43;1);

void initp()
p[0]&＃61;1;
for(int i&＃61;1;i p[i]&＃61;p[i-1]*131;
void init(int n)
memset(maze,0,sizeof(maze));
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;)
dp[i][j]&＃61;1;
memset(hash_1,0,sizeof(hash_1));
memset(hash_2,0,sizeof(hash_2));
int main()
// freopen("input.txt","r",stdin);
int n;
initp();
while(scanf("%d",&n)!&＃61;EOF&&n)

init(n);
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
scanf("%s",maze[i]&＃43;1);
hash_(n);
int mmax&＃61;1;
for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;)
for(int j&＃61;n-1;j>&＃61;1;j--)

int k&＃61;dp[i-1][j&＃43;1];
ULL a&＃61;hash_1[i][j&＃43;k]-hash_1[i][j-1]*p[k&＃43;1];
ULL b&＃61;hash_2[i-k][j]-hash_2[i&＃43;1][j]*p[k&＃43;1];
if(a&＃61;&＃61;b)
dp[i][j]&＃61;k&＃43;1;
else

int l&＃61;1,r&＃61;k;
int ans&＃61;0;
while(l<&＃61;r)

int mid&＃61;(l&＃43;r)/2;
ULL a&＃61;hash_1[i][j&＃43;mid]-hash_1[i][j-1]*p[mid&＃43;1];
ULL b&＃61;hash_2[i-mid][j]-hash_2[i&＃43;1][j]*p[mid&＃43;1];
if(a&＃61;&＃61;b)

ans&＃61;mid;
l&＃61;mid&＃43;1;

else

r&＃61;mid-1;


dp[i][j]&＃61;ans&＃43;1;

mmax&＃61;max(mmax,dp[i][j]);

cout<









return 0;

 


推荐阅读
author-avatar
手机用户2502856053
这个家伙很懒，什么也没留下！
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有